#include <stdio.h>
#include <stdlib.h>

//top变量时刻表示栈顶元素所在位置
int top=-1;
//二叉树节点结构
typedef struct binaryTreeNode {
    int data;   //数据域
    struct binaryTreeNode * leftChild, * rightChild;    //左右孩子指针
}binaryTreeNode_t, *binaryTree;

//初始化树的函数
void createBinaryTree(binaryTree * T){
    *T = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->data = 1;
    //根节点左孩子
    (*T)->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild = NULL;
    (*T)->leftChild->data = 2;
    (*T)->leftChild->rightChild = NULL;
    //根节点右孩子
    (*T)->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild = NULL;
    (*T)->rightChild->data = 3;
    (*T)->rightChild->rightChild = NULL;
    //根节点左孩子的左孩子
    (*T)->leftChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->leftChild->leftChild = NULL;
    (*T)->leftChild->leftChild->data = 4;
    (*T)->leftChild->leftChild->rightChild = NULL;
    //根节点左孩子的右孩子
    (*T)->leftChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->leftChild->rightChild->leftChild = NULL;
    (*T)->leftChild->rightChild->data = 5;
    (*T)->leftChild->rightChild->rightChild = NULL;
    //根节点右孩子的左孩子
    (*T)->rightChild->leftChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->leftChild->leftChild = NULL;
    (*T)->rightChild->leftChild->data = 6;
    (*T)->rightChild->leftChild->rightChild = NULL;
    //根节点右孩子的右孩子
    (*T)->rightChild->rightChild = (binaryTreeNode_t *)malloc(sizeof(binaryTreeNode_t));
    (*T)->rightChild->rightChild->leftChild = NULL;
    (*T)->rightChild->rightChild->data = 7;
    (*T)->rightChild->rightChild->rightChild = NULL;
}

//前序和中序遍历使用的进栈函数
void push(binaryTreeNode_t **a, binaryTreeNode_t *elem) {
    a[++top] = elem;
}

//弹栈函数
void pop() {
    if(top == -1) {
        return;
    }
    top--;
}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(binaryTreeNode_t * elem) {
    printf("%d ", elem->data);
}

//拿到栈顶元素
binaryTreeNode_t * getTop(binaryTreeNode_t ** a) {
    return a[top];
}

//中序遍历非递归算法
void INOrderTraverse1(binaryTree Tree) {
    //定义一个顺序栈
    binaryTreeNode_t *a[20];
    //临时指针
    binaryTreeNode_t *p;
    //根结点进栈
    push(a, Tree);
    //top!=-1说明栈内不为空，程序继续运行
    while (top != -1)
    {
        //取栈顶元素，且不能为NULL
        while ((p=getTop(a)) && p)
        {
            //将该结点的左孩子进栈，如果没有左孩子，NULL进栈
            push(a, p->leftChild);
        }
        //跳出循环，栈顶元素肯定为NULL，将NULL弹栈
        pop();
        if(top != -1) {
            //取栈顶元素
            p = getTop(a);
            //栈顶元素弹栈
            pop();
            displayElem(p);
            //将p指向的结点的右孩子进栈
            push(a, p->rightChild);
        }
    }
}

//中序遍历非递归算法
void INOrderTraverse2(binaryTree Tree) {
    //定义一个顺序栈
    binaryTreeNode_t *a[20];
    //临时指针
    binaryTreeNode_t *p;
    p = Tree;
    //当p为NULL或者栈为空时，表明树遍历完成
    while (p || top != -1)
    {
        //如果p不为NULL，将其压栈并遍历其左子树
        if(p) {
            push(a, p);
            p = p->leftChild;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
        else {
            p=getTop(a);
            pop();
            displayElem(p);
            p = p->rightChild;
        }
    }
    
}

int main(int argc, char * argv[]) {
    binaryTree Tree;
    createBinaryTree(&Tree);
    printf("中序遍历1: \n");
    INOrderTraverse1(Tree);
    printf("\n中序遍历2: \n");
    INOrderTraverse2(Tree);
    return 0;
}